package com.peng.leetcode.graph;

import java.util.*;

/**
 * FindOrder
 * 210. 课程表 II
 *
 * 现在你总共有 n 门课需要选，记为 0 到 n-1。
 *
 * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
 *
 * 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
 *
 * 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
 *
 * 链接：https://leetcode-cn.com/problems/course-schedule-ii
 *
 * @author: lupeng6
 * @create: 2021/1/7 19:40
 */
public class FindOrder {

    public static void main(String[] args) {
        int[][] prerequisites = {{0, 1}, {0, 3}, {1, 4}, {2, 4}, {1, 3}, {3, 4}};
        int[] order = new FindOrder().findOrder(5, prerequisites);
        Arrays.stream(order).forEach(System.out::print);
    }

    /**
     * 图,
     * 统计入度, 统计边
     * 从入度为0的开始, 广度优先搜索.
     *
     *
     * @author lupeng6
     * @date 2021/1/7 19:41
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] order = new int[numCourses];
        int index = 0;
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            int[] prerequisite = prerequisites[i];
            int target = prerequisite[0];
            int orange = prerequisite[1];
            inDegree[target]++;
            List<Integer> integers = adj.getOrDefault(orange, new ArrayList<>());
            integers.add(target);
            adj.put(orange, integers);
        }
        Queue<Integer> queue = new ArrayDeque<>(numCourses);
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer orange = queue.poll();
            order[index++] = orange;
            List<Integer> targets = adj.get(orange);
            if (targets == null) {
                continue;
            }
            for (Integer nextOrange : targets) {
                inDegree[nextOrange]--;
                if (inDegree[nextOrange] == 0) {
                    queue.offer(nextOrange);
                }
            }
        }
        if (index == numCourses) {
            return order;
        } else {
            return new int[]{};
        }
    }
}
